5、四平方和
题目 四平方和
思路分析
（我只能说 这题暴力在蓝桥杯里面可以ac 不需要用二分或者哈希）
求出三个后可以确定最后一个 三重循环暴力解决
其实求出两个 看差的一个t是否也能被两个凑出来 从而优化
这个看t是否能被两个凑出来 可以用二分 也可以直接用哈希
两个问题：
第一个问题：二分和哈希的代码b不是从a开始遍历，如何保证a <=b
第二个问题：二分和哈希的方式是如何保证b <= c的
两个问题都可以通过观察枚举顺序以及反证法来解答
第一个问题：假如存在一对a,b为答案，且a>b，那么b,a这一对数对在之前肯定已经枚举过的，因此找到的答案应该是b,a，因此这样并不会让找错答案，顶多是多枚举了一些
第二个问题：注意看二分和哈希分别做了什么事，二分是找到最小的大于等于n−a×a−b×b 的数对，哈希是找到等于n−a×a−b×b的数对，然后由枚举的顺序可以知道，a≤b,c≤d一定成立，且枚举的时候，a×a,b×b也是从小到大枚举的，换言之n−a×a−b×b是从大到小出现的，假设存在答案a,b,c,d，且b>c，那么一定有a×a+b×b>a×a+c×c，因此a,c应当比a,b先出现，而此时a,c,b,d是一组合法的答案。
代码实现
暴力\(O(n^3)\)
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 2500010;
int n;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n;
for (int a = 0; a * a <= n; a ++ ){
for (int b = a; a * a + b * b <= n; b ++ ){
for (int c = b; a * a + b * b + c * c <= n; c ++ ){
int t = n - a * a - b * b - c * c;
int d = sqrt(t);
if (d * d == t){
printf("%d %d %d %d\n", a, b, c, d);
return 0;
}
}
}
}
}
二分\(O(n2logNn)\)
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 2500010;
struct Sum{
int s, c, d;
bool operator< (const Sum &t)const{
if (s != t.s) return s < t.s;
if (c != t.c) return c < t.c;
return d < t.d;
}
}sum[N];
int n, m;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n;
for (int c = 0; c * c <= n; c ++ )
for (int d = c; c * c + d * d <= n; d ++ )
sum[m ++ ] = {c * c + d * d, c, d};
sort(sum, sum + m);
for (int a = 0; a * a <= n; a ++ ){
for (int b = 0; a * a + b * b <= n; b ++ ){
int t = n - a * a - b * b;
int l = 0, r = m - 1;
while (l < r){
int mid = l + r >> 1;
if (sum[mid].s >= t)
r = mid;
else
l = mid + 1;
}
if (sum[l].s == t){
printf("%d %d %d %d\n", a, b, sum[l].c, sum[l].d);
return 0;
}
}
}
return 0;
}
哈希表\(O(n^2)\)
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 2500010;
int n, m;
unordered_map<int, PII> S;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n;
for (int c = 0; c * c <= n; c ++ ){
for (int d = c; c * c + d * d <= n; d ++ ){
int t = c * c + d * d;
if (S.count(t) == 0)
S[t] = {c, d};
}
}
for (int a = 0; a * a <= n; a ++ ){
for (int b = 0; a * a + b * b <= n; b ++ ){
int t = n - a * a - b * b;
if (S.count(t)){
printf("%d %d %d %d\n", a, b, S[t].x, S[t].y);
return 0;
}
}
}
return 0;
}
💬 评论